package 算法.练习;

import java.util.HashMap;

/**
 * @author:谢君臣
 * @Date:2021/8/24-22:42
 * @version:1.0
 * @function:
 */
public class LRU {

    private int capacity;
    private LinkedNode head;
    private LinkedNode tail;
    private HashMap<String, LinkedNode> hashMap;

    class LinkedNode {
        private String key;
        private Object val;
        private LinkedNode per;
        private LinkedNode next;

        public LinkedNode() {
        }

        public LinkedNode(String key, Object val) {
            this.key = key;
            this.val = val;
        }

        public LinkedNode(String key, Object val, LinkedNode per, LinkedNode next) {
            this.key = key;
            this.val = val;
            this.per = per;
            this.next = next;
        }
    }

    public LRU() {
    }

    public LRU(int capacity) {
        this.capacity = capacity;
        this.hashMap = new HashMap<>();
    }

    public Object get(String key) {
        if (hashMap.containsKey(key)) { //缓存命中
            LinkedNode node = hashMap.get(key); // 找到命中的缓存
            if (node != head) {
                if (node == tail) { // 尾节点
                    tail = node.per;
                    tail.next = null;
                } else {  // 中间节点
                    node.per.next = node.next;
                    node.next.per = node.per;
                }
                node.per = null;
                node.next = head;
                head.per = node;
                head = node;
            }
            return node.val;
        } else
            return null;
    }

    public Object put(String key, Object o) {
        Object val = null;
        if (hashMap.containsKey(key)) { //缓存中存在该key,则替换
            LinkedNode node = hashMap.get(key);
            val = node.val;
            node.val = o;
        } else {
            LinkedNode node = new LinkedNode(key, o);
            if (head == null) {
                head = node;
                tail = head;
            } else {
                head.per = node;
                node.next = head;
                head = node;
            }
            hashMap.put(node.key,node);
            if (hashMap.size() > capacity)
                resize(); // 检查容量
        }
        return val; // 返回旧值
    }

    public void clear() {
        hashMap.clear();
        tail = null;
        head = null;
    }

    private void resize() {
        hashMap.remove(tail.key, tail);
        tail = tail.per;
        tail.next.per = null;
        tail.next = null;
    }

}
